package com.mjx.algorithm;

import com.mjx.algorithm.tool.Tools;

/**
 * 插入排序:标记位左边是排好序的，右边是未排序的。每次从排好序的数组中查找条件，一直右移，标记位数据保存在临时变量中，直到找到符合条件的空位，再将其插入，标记位右移，重复
 * 效率:O(N2)
 * Created by meijingxiang on 2017/2/4.
 */
public class InsertSort {
    public static void insertSort(int []array){
        insertSort(array,0,array.length - 1);
    }

    public static void insertSort(int []array, int left, int right){
        //标记位
        int flag = left + 1;
        int pos;
        for (; flag <= right; flag++) {
            //暂时将标记位取出保存
            int temp = array[flag];
            pos = flag;
            while (pos > 0 && array[pos - 1] > temp){
                array[pos] = array[pos - 1];
                pos--;
            }
            array[pos] = temp;
        }
    }

    public static void main(String[] args) {
        int []array=Tools.generaterArray(20);
        Tools.printIntArray(array);
        insertSort(array);
        Tools.printIntArray(array);
    }
}
